#include <map>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

//
// 1 <= n <= 3999
// i2r(1994) -> "MCMXCIV"
//
// 从十进制数字的高位向低位运算
//                商      余数
// 1994 / 1000    1      994     M
// 994  / 100     9      94      M + CM
// 94   / 10      9      4       M + CM + XC
// 4    / 1       4      0       M + CM + XC + IV
string i2r(int n) {
  // 1 -> "I"
  // 4 -> "IV"
  vector<int> sym2num = {1000, 900, 500, 400, 100, 90 ,50, 40, 10, 9, 5, 4, 1};
  vector<string> sym = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

  string result;
  int i = 0;

  while (n > 0) {
    for (int j = 0; j < n / sym2num[i]; ++j) {
      result += sym[i];
    }

    n = n % sym2num[i];
    ++i;
  }

  return result;
}

int main(int argc, char const *argv[])
{
  /* code */
  return 0;
}
